package 中等.找规律;

/**
 * 我们构建了一个包含 n 行( 索引从 1  开始 )的表。首先在第一行我们写
 * 上一个 0。接下来的每一行，将前一行中的0替换为01，1替换为10。
 * 例如，对于 n = 3 ，第 1 行是 0 ，第 2 行是 01 ，第3行是 0110 。
 * 给定行数 n 和序数 k，返回第 n 行中第 k 个字符。（ k 从索引 1 开始）
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/k-th-symbol-in-grammar
 */
public class 第K个语法符号_779 {

    public static void main(String[] args) {

        System.out.println(kthGrammar(3, 3));

    }

    /**
     * 0
     * 01
     * 0110
     * 01101001
     * 第 i 行是由第 i-1 行 + 第 i-1 行每位取反得到的
     * 位运算符进行模拟取反
     * 1 ^ 1 = 0
     * 1 ^ 0 = 1
     * 第 i 行的位个数为 i 的 n-1 次方，即 1 << (n-1)
     */
    public static int kthGrammar(int n, int k) {
        if (n == 1) {
            return 0;
        }
        // 处于后半段，取反
        if (k > (1 << (n - 1)) / 2) {
            return 1 ^ kthGrammar(n - 1, k - (1 << (n - 1)) / 2);
        } else {
            // 前半段和 i-1 位一致
            return kthGrammar(n - 1, k);
        }
    }

}
